package org.ala.ohter;

import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.stream.IntStream;

/**
 * Q2398的变体，子数组改为子序列
 *
 * 你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
 *
 * 运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
 *
 * 请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
 *
 *
 *
 * 示例 1：
 *
 * 输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
 * 输出：3
 * 解释：
 * 可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
 * 选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
 * 可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。
 * 示例 2：
 *
 * 输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
 * 输出：0
 * 解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。
 *
 *
 * 提示：
 *
 * chargeTimes.length == runningCosts.length == n
 * 1 <= n <= 5 * 104
 * 1 <= chargeTimes[i], runningCosts[i] <= 105
 * 1 <= budget <= 1015
 *
 * @author ala
 * @data 2024-09-13 09:20
 */
public class Q2398 {

    public static void main(String[] args) {
        Q2398 q = new Q2398();

//        int[] chargeTimes = {3,6,1,3,4},
//              runningCosts = {2,1,3,4,5};
//        int budget = 25;

//        int[] chargeTimes = {11,12,1},
//              runningCosts = {1,8,1};
//        int budget = 19;

        int[] chargeTimes = {19,63,21,8,5,46,56,45,54,30,92,63,31,71,87,94,67,8,19,89,79,25},
              runningCosts = {91,92,39,89,62,81,33,99,28,99,86,19,5,6,19,94,65,86,17,10,8,42};
        int budget = 85;

        System.out.println(q.maximumRobots(chargeTimes, runningCosts, budget));
    }

    /**
     * 子序列
     */
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        N = chargeTimes.length;
        return V1(chargeTimes, runningCosts, budget);
    }
    protected int N;
    /**
     *  排序 + 大根堆贪心
     *  1）chargeTimes 升序，那么从左往右遍历时就可以不考虑前面还有比当前charge大的情况
     *  2）贪心的想：如果 c + k * sum 超了，那应该往前舍弃 runningCosts 最大的，才能给后面的元素尽量腾出空间（而且 k 越大舍弃他的价值越大）
     *      应该需要完整证明（舍弃 r 中较大的而不是舍弃更大的 c，当 k 到达一定长度后价值才能体现出来），可是我不会。。。
     *      舍弃的时候需要特判一下，如果当前遍历的 r 就是最大的，那直接舍弃当前遍历元素
     */
    protected int V1(int[] chargeTimes, int[] runningCosts, long budget) {
        //  按 runningCosts 升序
        int[] idx = IntStream.range(0, N).boxed().sorted((i1, i2) -> chargeTimes[i1] - chargeTimes[i2]).mapToInt(i -> i.intValue()).toArray();
        //  大根堆（为了打印方便，这里存的下标，但直接存run更方便）
        PriorityQueue<Integer> heap = new PriorityQueue<>((i1, i2) -> runningCosts[i2] - runningCosts[i1]);
        int res = 0, k = 0, sum = 0;
        for (int i = 0 ; i < N ; i++) {
            int ii = idx[i];
            int c = chargeTimes[ii], r = runningCosts[ii];

            //  如果 r 就是当前最大 run
            if (k > 0 && r > runningCosts[heap.peek()]) {
                //  如果此时超了，直接放弃本轮
                int v = c + (k + 1) * (sum + r);
                if (v > budget) {continue;}
                //  如果没超加到结果中
                heap.offer(ii); k++; sum += r;
            }
            //  如果 r 不是当前最大 run，那 c 可以保持不变
            else {
                int v = c + (k + 1) * (sum + r);
                while (k > 0 && v > budget) {
                    sum -= runningCosts[heap.poll()];
                    k--;
                    v = c + (k + 1) * (sum + r);
                }
                //  有可能 heap 出完了，单单一个当前元素就超了
                v = c + (k + 1) * (sum + r);
                if (v > budget) {continue;}
                heap.offer(ii); k++; sum += r;
            }
            res = Math.max(res, k);
        }
        return res;
    }
}
